// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-19 09:45
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.ArraysTrain;

import org.junit.jupiter.api.Test;

import java.util.*;

public class FourSum {
    /**
     * 四数之和 -> 二进制枚举 -> 重复列表去重
     * 这个方法可能会出现数据溢出的情况
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = 1 << nums.length;
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            if (Integer.bitCount(i) == 4) {
                List<Integer> tmp = new ArrayList<Integer>();
                int t = 0;
                for (int j = 0; j < 32; j++) {
                    if (((i >> j) & 1) == 1) {
                        t += nums[j];
                        tmp.add(nums[j]);
                    }
                }
                if (t == target) {
                    res.add(tmp);
                }
            }
            for (List<Integer> re : res) {
                re.sort(Comparator.naturalOrder());
            }
            DRT(res);
        }
        return res;
    }

    /**
     * 对给定列表进行去重 -> 即相同位置上的元素相同 -> N叉树
     *
     * @param res
     */
    private void DR(List<List<Integer>> res) {
        Node node = new Node();
        for (List<Integer> re : res) {
            node.insert(re);
        }
        ArrayList<Integer> tmp = new ArrayList<>();
        res.clear();
        node.getRes(node.root, tmp, res);
    }


    class Node {
        class NumberNode {
            boolean end;
            NumberNode[] tns = new NumberNode[20];
        }

        NumberNode root;

        public Node() {
            root = new NumberNode();
        }

        public void insert(List<Integer> list) {
            NumberNode p = root;
            for (int i = 0; i < list.size(); i++) {
                int u = list.get(i) + 10;
                if (p.tns[u] == null) {
                    p.tns[u] = new NumberNode();
                }
                p = p.tns[u];
            }
            p.end = true;
        }

        /**
         * 通过遍历字典树获取不重复的数字列表
         *
         * @return
         */
        public List<List<Integer>> getRes(NumberNode p, List<Integer> tmp, List<List<Integer>> res) {
        /*
            从根节点开始遍历遇到叶子叶子节点就讲数据存入结果中
         */
            for (int i = 0; i < 20; i++) {
                if (p.tns[i] != null) {
                    tmp.add(i - 10);
                /*
                    因为存储数据的时候都是四个整数一起存，所以取数据的时候都是四个整数一起取
                 */
                    if (p.tns[i].end) {
                        List<Integer> integers = new ArrayList<>(tmp);
                        res.add(integers);
                    }
                    getRes(p.tns[i], tmp, res);
                    tmp.remove(tmp.size() - 1);
                }
            }
            return res;
        }
    }


    /**
     * 简单去重 -> 不能存在相同的数字组合
     */
    private void DRT(List<List<Integer>> res) {
        List<List<Integer>> tmp = new ArrayList<>();
        for (int i = 0; i < res.size(); i++) {
            boolean flag = false;
            here:
            for (int j = 0; j < i; j++) {
                int t = 0;
                for (int k = 0; k < 4; k++) {
                    t = res.get(j).get(k) - res.get(i).get(k);
                    if (t != 0) {
                        continue here;
                    }
                    if (k == 3) {
                        flag = true;
                        break here;
                    }
                }
            }
            if (!flag) {
                tmp.add(res.get(i));
            }
        }
        res.clear();
        res.addAll(tmp);
    }

    @Test
    public void shout() {
//        int[] test = {1, 0, -1, 0, -2, 2};
//        int target = 0;
//        int[] test = {-5, 5, 4, -3, 0, 0, 4, -2};
//        int target = 4;
//        int[] test = {0, 2, 2, 2, 10, -3, -9, 2, -10, -4, -9, -2, 2, 8, 7};
//        int target = 6;
        int[] test = {-3, 0, 7, -2, -6, -5, 1, 5, -1, -8, -9, -8, 7, 1, 1, 3, 1, 10};
        int target = 0;
        System.out.println(fourSum(test, target));
    }
}
